package ch3.part3;

import java.util.Arrays;

/**
 * 二叉堆的实现，及构建、插入、删除的代码实现
 * 以最小堆为例
 *
 * @author liuwanxiang
 * @version 2019/05/17
 */
public class BinaryHeap {

    /**
     * 基于已有的二叉堆，对新加进来的元素做上浮处理
     *
     * @param array 二叉堆
     */
    private static void upAdjust(int[] array) {
        int childIndex = array.length - 1;
        int parentIndex = (childIndex - 1) / 2;
        int tempData = array[childIndex];

        while (childIndex > 0 && tempData < array[parentIndex]) {
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (parentIndex - 1) / 2;
        }
        array[childIndex] = tempData;
    }

    /**
     * 基于已有的二叉堆，对指定节点的元素做下沉处理
     *
     * @param array       二叉堆
     * @param parentIndex 需要做下沉处理的元素
     */
    private static void downAdjust(int[] array, int parentIndex) {
        int tempData = array[parentIndex];
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < array.length) {
            if (childIndex + 1 < array.length && array[childIndex + 1] < array[childIndex]) {
                childIndex++;
            }
            if (tempData <= array[childIndex]) {
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = childIndex * 2 + 1;
        }
        array[parentIndex] = tempData;
    }

    /**
     * 基于数据构建二叉堆
     *
     * @param array 输入数组
     */
    private static void buildHeap(int[] array) {
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            downAdjust(array, i);
        }
    }

    public static void main(String[] args) {
        int[] heap = new int[]{1, 3, 2, 6, 5, 7, 8, 9, 10, 4};
        upAdjust(heap);
        System.out.println(Arrays.toString(heap));

        //---------------------------

        heap = new int[]{10, 3, 2, 6, 5, 7, 8, 9};
        downAdjust(heap, 0);
        System.out.println(Arrays.toString(heap));

        //---------------------------
        heap = new int[]{1, 9, 8, 2, 3, 7, 4, 6, 5, 0};
        buildHeap(heap);
        System.out.println(Arrays.toString(heap));
    }

}
